{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Full Binary Tree（满二叉树）\n",
    "\n",
    "[@mjd507][1] ｜ [WeChat Channel（微信公众号）][2]\n",
    "\n",
    "![Logo](DP-70.png)\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/zWioGf4w116GiHRrhWEy8A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, remove the nodes in which there is only 1 child, so that the binary tree is a full binary tree.\n",
    "\n",
    "So leaf nodes with no children should be kept, and nodes with 2 children should be kept as well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;给定一棵二叉树，移除只有一个孩子的节点使二叉树成为满二叉树。\n",
    "\n",
    "&emsp;&emsp;所以，没有孩子的叶子节点应该被保留，同时拥有2个孩子的节点也应该被保留。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting Point（初始模板）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value: int, left=None, right=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.value = value\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        q = deque()\n",
    "        q.append(self)\n",
    "        result = ''\n",
    "        while len(q) > 0:\n",
    "            num = len(q)\n",
    "            while num > 0:\n",
    "                n = q.popleft()\n",
    "                result += str(n.value)\n",
    "                if n.left is not None:\n",
    "                    q.append(n.left)\n",
    "                if n.right is not None:\n",
    "                    q.append(n.right)\n",
    "                num -= 1\n",
    "            if len(q) > 0:\n",
    "                result += '\\n'\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fullBinaryTree(node: Node) -> Node:\n",
    "    if node is None:\n",
    "        return None\n",
    "    hasleft = (node.left is not None)\n",
    "    hasright = (node.right is not None)\n",
    "    if (hasleft and hasright) or (not hasleft and not hasright):\n",
    "        node.left = fullBinaryTree(node.left)\n",
    "        node.right = fullBinaryTree(node.right)\n",
    "    elif hasleft:\n",
    "        node = fullBinaryTree(node.left)\n",
    "    else:\n",
    "        node = fullBinaryTree(node.right)\n",
    "    return node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases（测试样例）\n",
    "\n",
    "Given a tree like: （给定一棵这样的树：）\n",
    "```text\n",
    "#     1\n",
    "#    / \\\n",
    "#   2   3\n",
    "#  /   / \\\n",
    "# 0   9   4\n",
    "```\n",
    "\n",
    "We want a tree be solved like this: （我们希望得到这样的树：）\n",
    "```text\n",
    "#   1\n",
    "#  / \\ \n",
    "# 0   3\n",
    "#    / \\\n",
    "#   9   4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "03\n",
      "94\n"
     ]
    }
   ],
   "source": [
    "tree = Node(1, Node(2, Node(0)), Node(3, Node(9), Node(4)))\n",
    "print(fullBinaryTree(tree))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
